package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //验证二叉搜索树
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode() {}
         *     TreeNode(int val) { this.val = val; }
         *     TreeNode(int val, TreeNode left, TreeNode right) {
         *         this.val = val;
         *         this.left = left;
         *         this.right = right;
         *     }
         * }
         */
        class Solution {

            public boolean isValidBST(TreeNode root) {
                return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
            }

            private boolean isValid(TreeNode node, long low, long high) {
                // 1) 空树合法
                if (node == null) return true;

                // 2) 当前节点必须在 (low, high) 的开放区间内（严格不等）
                if (node.val <= low || node.val >= high) return false;

                // 3) 递归校验左右子树，并分别更新家规
                return isValid(node.left, low, node.val)
                        && isValid(node.right, node.val, high);
            }
        }

        //二叉搜索树的第K小元素
        class Solution2 {
            private int remain; // 还需要访问多少个节点
            private int ans;

            public int kthSmallest(TreeNode root, int k) {
                this.remain = k;
                this.ans = -1;
                dfs(root);
                return ans;
            }

            private void dfs(TreeNode node) {
                if (node == null || remain == 0) return; // 基例 + 剪枝

                dfs(node.left);                // 先走左
                if (remain == 0) return;       // 左子树已经找到就不要再处理当前与右子树

                if (--remain == 0) {           // 访问“当前”节点
                    ans = node.val;
                    return;                    // 已经确定答案，交给入口剪枝阻断后续递归
                }

                dfs(node.right);               // 再走右
            }
        }
    }
}